import java.util.ArrayList;

public class Solution {
//    给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
//    示例 1：
//    输入:a = "11", b = "1"
//    输出："100"
//    示例 2：
//    输入：a = "1010", b = "1011"
//    输出："10101"
    public String addBinary(String a, String b) {
        int cur1 = a.length() - 1;
        int cur2 = b.length() - 1;
        int t = 0;
        StringBuilder ret = new StringBuilder();
        while(cur1 >= 0 || cur2 >= 0 || t > 0){
            if(cur1 >= 0 && a.charAt(cur1) > '0'){
                t += 1;
            }
            cur1--;
            if(cur2 >= 0 && b.charAt(cur2) > '0'){
                t += 1;
            }
            cur2--;
            ret.append(t % 2);
            t /= 2;
        }
        ret.reverse();
        return ret.toString();
    }
}